package part1.q4;

import java.util.Stack;

public class StackSort {
	
	
	
	/**
	 * 用一个栈实现另一个栈的排序
	 */
	public static void sortStackByStack(Stack<Integer> stack) {
		Stack<Integer> help = new Stack<Integer>();
		while(!stack.isEmpty()) {
			int cur = stack.pop();
			while(!help.isEmpty() && help.peek() < cur) {
				stack.push(help.pop());
			}
			help.push(cur);
		}
		
		while(!help.isEmpty()) {
			stack.push(help.pop());
		}
	}
	
	/**
	 * stack				help
	 * 						 0
	 * 						 1
	 * 						 2
	 * 						 3
	 * 						 4
	 * 						 5
	 * 	 					 7
	 *         			  
	 *   
	 *   -------------------------------
	 *   1.  cur = 0     --> help  0
	 *   2.  cur = 5     --> stack 0   help --> 0
	 *   	       --> help  5
	 *   3.  cur = 0     --> help  0
	 *   4.  cur = 2     --> stack 0   help --> 0
	 *             --> help  2
	 *   5.  cur = 0     
	 *             --> help  0
	 *   6   cur = 7     --> stack 0   help --> 0
	 *   				 --> stack 2   help --> 2
	 *   				 --> stack 5   help --> 5
	 *             --> help  7
	 *   7.  cur = 5     
	 *             --> help  5
	 *   8.  cur = 2     
	 *   		   --> help  2
	 *   9.  cur = 0   
	 *   		   --> help  0
	 *   10. cur = 1     --> stack 0   
	 *   		   --> help  1
	 *   11. cur = 0
	 *   		   --> help  0
	 *   12. cur = 4     --> stack 0    help --> 0
	 *   				 --> stack 1    help --> 1
	 *   				 --> stack 2    help --> 2
	 *   		   --> help 4
	 *   13. cur = 2 
	 *   		   --> help 2
	 *   14. cur = 1 
	 *   		   --> help 1 
	 *   15. cur = 0
	 *   		   --> help 0
	 *   16. cur = 3     --> stack 0    help --> 0
	 *   				 --> stack 1    help --> 1
	 *   				 --> stack 2    help --> 2
	 *   		   --> help 3
	 *   17. cur = 2     
	 *   		   --> help 2
	 *   18. cur = 1     
	 *             --> help 1
	 *   19. cur = 0
	 *   		   --> help 0
	 *   
	 *   
	 *   
	 *   
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		Stack<Integer> stack = new Stack<Integer>();
		stack.push(3);
		stack.push(4);
		stack.push(1);
		stack.push(7);
		stack.push(2);
		stack.push(5);
		stack.push(0);
		sortStackByStack(stack);
	}
	
}
